import java.util.Stack;

/**
 * @作者 钟先崟
 * @时间 2023-03-05 11:21
 * @说明 32. 最长有效括号
 * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
 * 示例 1：
 * 输入：s = "(()"
 * 输出：2
 * 解释：最长有效括号子串是 "()"
 */
public class Solution {
    public static void main(String[] args) {
        System.out.println(longestValidParentheses("(()"));
        System.out.println(longestValidParentheses(")()())"));
        System.out.println(longestValidParentheses("()()"));
    }

    /**
     * 执行用时：
     * 11 ms
     * , 在所有 Java 提交中击败了
     * 6.38%
     * 的用户
     * 内存消耗：
     * 41.5 MB
     * , 在所有 Java 提交中击败了
     * 39.45%
     * 的用户
     *
     * @param s
     * @return
     */
    public static int longestValidParentheses(String s) {
        Stack<Character> stackCh = new Stack<>();
        Stack<Integer> stackInt = new Stack<>();
        int[] arr = new int[s.length()];
        for (int i = 0; i < s.length(); i++) {
            if (stackCh.empty()) {
                stackCh.push(s.charAt(i));
                stackInt.push(i);
            } else {
                Character peek = stackCh.peek();
                if (peek == '(' && s.charAt(i) == ')') {
                    stackCh.pop();
                    arr[stackInt.pop()] = 1;
                    arr[i] = 1;
                } else {
                    stackCh.push(s.charAt(i));
                    stackInt.push(i);
                }
            }
        }
        int num = 0;
        int max = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == 1) num++;
            else {
                if (max < num) max = num;
                num = 0;
            }
        }
        if (max < num) max = num;
        return max;
    }
}
